package l.l.w.leetcode._134_GasStation;

/**
 * Created by llw on 2018/5/28/0028.
 */
public class _134_GasStation {
    public int canCompleteCircuit(int[] gas, int[] cost) {

        int total = 0, tank = 0;
        int start = 0;
        for(int i = 0; i < gas.length; ++i){
            tank += gas[i] - cost[i];
            if(tank < 0){
                total += tank;
                tank = 0;
                start = i + 1;
            }
        }
        return total + tank >=  0 ? start : -1;
        /*if(gas == null || gas.length == 0) return -1;
        int len = gas.length;
        int[] gsum = new int[len];
        int[] csum = new int[len];
        gsum[0] = gas[0];
        csum[0] = cost[0];
        for(int i = 1; i < len; ++i){
            gsum[i] = gsum[i-1] + gas[i];
            csum[i] = csum[i-1] + cost[i];
        }
        if(gsum[len-1] < csum[len-1]) return -1;
        int i = len - 2;
        for(; i >= 0; --i){
            if(gsum[i] < csum[i])break;
        }
        if(i < 0) return 0;
        if(gas[i] >= cost[i]) return i;
        return i+1;*/
    }
/*[5,1,2,3,4]
[4,4,1,5,1]


[1,2,3,4,5]
[3,4,5,1,2]
*/
    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};

        int result = new _134_GasStation().canCompleteCircuit(gas, cost);
        System.out.println(result);
    }
}
